#!/usr/env/bin python
# -*- coding: utf-8 -*-

# @Time    : 2020-07-25 9:22 上午
# @Author  : yangdy
# @File    : my_methods
# @Software: PyCharmCE
from typing import List
from functools import lru_cache
from itertools import accumulate
from bisect import bisect_right, bisect_left, insort

import collections
from collections import defaultdict

import heapq


def list_display(_list_a):
    for _item_i, _item in enumerate(_list_a):
        print(_item_i, _item)


def work(questions, func):
    for qi, q in enumerate(questions):
        print(f'#{qi}:', q)
        print('ans:', func(q))


def mk_tree(data, TreeNode):
    root = None
    if not data:
        return root
    root = TreeNode(data[0])
    i = 1
    que = [root]
    while que and i < len(data):
        new_que = []
        for x in que:
            if not x:
                continue
            if i >= len(data):
                break
            left = TreeNode(data[i]) if data[i] is not None else None
            i += 1
            x.left = left
            if left:
                new_que.append(left)
            if i < len(data):
                right = TreeNode(data[i]) if data[i] is not None else None
                i += 1
                x.right = right
                if right:
                    new_que.append(right)
        que = new_que

    return root


def find_tree(root, value):
    if not root:
        return root
    p = root
    while p:
        if p.val > value:
            p = p.left
        elif p.val < value:
            p = p.right
        else:
            return p
    return None


def display(root):
    print('----')

    def _display(rt, dep=0):
        if not rt:
            return
        _display(rt.right, dep+1)
        print(' '*dep, rt.val)
        _display(rt.left, dep+1)
    _display(root)
    print('----')


def mk_list(data, ListNode):
    ld = len(data)
    q = None
    for i in range(ld-1, -1, -1):
        p = ListNode(data[i])
        p.next = q
        q = p
    return q


def display_list(head):
    while head:
        print(head.val, end='')
        if head.next:
            print('->', end='')
        head = head.next
    print()

